//https://www.luogu.com.cn/problem/P1020
//题意：有一串数，输出最长不上升子序列长度，以及最少可以由几个不上升子序列组成
//思路：最长不上升子序列用dp，每次碰到一个点如果能放，在末尾直接放，len++，不能则更新队中第一个大于它的数
//第二问等价于求最长上升子序列（严格），Dilworth 定理（将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数）
#include<bits/stdc++.h>
using namespace std;
int n=0;
int len;
int a[100010];
int dp1[100005];
int dp[100010];
int main(){
	while(~scanf("%d",&a[++n]));
    n--;
	len=1;
	dp1[1]=a[1];
	for(int i=2;i<=n;i++){
		if(dp1[len]>=a[i]){
			dp1[++len]=a[i];
		}
		else{
			int pos=upper_bound(dp1+1,dp1+len+1,a[i],greater<int>())-dp1;
			dp1[pos]=a[i];
		}
	}//求最长不上升子序列
	printf("%d\n",len);
	len=1;
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		if(dp[len]<a[i]){
			dp[++len]=a[i];
		}
		else{
			int pos=lower_bound(dp+1,dp+len+1,a[i])-dp;
			dp[pos]=a[i];
		}
	}
	printf("%d",len);
}